import random
import time

# 定义常量
N = 100000

# --- 辅助函数 ---
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

# --- 快速排序 (Quick Sort) ---
def partition(arr, low, high):
    pivot = arr[high]
    i = (low - 1)
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            swap(arr, i, j)
    swap(arr, i + 1, high)
    return (i + 1)

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# --- 归并排序 (Merge Sort) ---
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# --- 堆排序 (Heap Sort) ---
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l

    if r < n and arr[r] > arr[largest]:
        largest = r

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        swap(arr, 0, i)
        heapify(arr, i, 0)

# --- 主执行部分 ---
if __name__ == "__main__":
    # 生成随机数
    random_numbers = [random.randint(0, N - 1) for _ in range(N)]

    # --- 快速排序 ---
    print("Python Quick Sort:")
    arr_qs = list(random_numbers) # 复制列表
    start_time = time.time()
    quick_sort(arr_qs, 0, N - 1)
    end_time = time.time()
    print(f"Time taken: {(end_time - start_time) * 1000:.2f} milliseconds")

    # --- 归并排序 ---
    print("Python Merge Sort:")
    arr_ms = list(random_numbers) # 复制列表
    start_time = time.time()
    merge_sort(arr_ms)
    end_time = time.time()
    print(f"Time taken: {(end_time - start_time) * 1000:.2f} milliseconds")

    # --- 堆排序 ---
    print("Python Heap Sort:")
    arr_hs = list(random_numbers) # 复制列表
    start_time = time.time()
    heap_sort(arr_hs)
    end_time = time.time()
    print(f"Time taken: {(end_time - start_time) * 1000:.2f} milliseconds")